#ifndef __disjointset_h__
#define __disjointset_h__

#include <iostream>
#include <iomanip>
#include <cassert>
#include <list>

using namespace std;

class DisjointSet
{
	int size;
	int *links;
	int *ranks;

public:
	DisjointSet(int size);
	~DisjointSet();

	int find(int i);
	bool join(int i, int j);

	friend ostream& operator<<(ostream &os, const DisjointSet &ds);
};

ostream& operator<<(ostream &os, const DisjointSet &ds);

#endif /* __disjointset_h__ */